Volodya's blog

STL Visualization

2009-06-06T21:24:00.006+04:00

As of today, KDevelop can nicely display std::vector. I'll probably omit the obvious snapshot, and will point to a mailing list post with instructions for trying it. Instead, I'll tell the story of this feature.

For its entire history, GDB did not have any official way to display types from the C++ Standard Library in a sensible way. Several third-party scripts appeared, written in GDB's internal scripting language. However, they were fairly limited. You had to explicitly run those scripts, and all you got was text output without structure, making robust IDE integration impossible. Also, GDB's scripting language is itself unpleasant, and does not even have access to internal data structures and functions. It was clear that we need a way to write pretty-printers using real scripting language, with full access to GDB data structures, and proper integration with frontend interface.

The first prototype of Python-based pretty printing was written by myself during free hack slot at a CodeSourcery company meeting. It took maybe 4 hours, if not less, and could display std::string as string automatically. Some 4 hours more lead to the first public prototype. This version could automatically display std::vector as "[1,2]". The second prototype could finally display elements of std::vector as children, like one would expect in a variables tree of a frontend, and even report when new elements are added to the vector. However, this version took a couple of days of work, exposed a mere 4 functions from GDB to Python, and was a mess internally. It was clearly already outside the "quick hack" range.

Those prototypes would never turn into anything, were it not for Tom Tromey and Thiago Bauermann, who started a project to add complete Python scripting to GDB. This is much more ambitious than just pretty-printing. In particular, it includes defining new commands in Python, with full access to GDB internals. You can read more details in a post series by Tom.

Pretty-printing became a part of that large effort, and was greatly improved. One of the most notable change was incremental fetch of children. According to the C++ standard, an object does not exist until its constructor has exited. However, gcc debug info just lists all local variables in a block. A naive pretty-printer, when invoked on such a variable, would likely go into uncharted part of memory trying to fetch all children, and never return. To fix this, the Python pretty-printers were designed to use incremental fetch, using Python iterators, and GDB MI interface was also adjusted to be more incremental (yes, it's a trend). Beyond that, we've spend at least 3 weeks iterating on finer details. The GDB patch was finally checked in on Sep 15, and KDevelop4 patch shortly after.

This is still early implementation, and might have bugs, but now it's out for everybody to try.

Linking 101

2009-06-01T14:41:00.004+04:00

Recently, I see more and more people having trouble with link-time errors—as if such an error is the worst kind of luck and cannot be fixed by mere mortals. There are many possible reasons, including Java as default language in universities, and alarming spread of header-only-philia, but that's for another post. Here, I want to give a simple diagnostic procedure for link-time errors.

Let's lay some groundwork first. If your job is programming in C++, you need to know what the -I and -L options do, and how they are different. Also, given a full path to a library file (with .a or .so or .lib extension), you should be able to link to that file—in two different ways. If you don't know any of the above already, all hope is lost—you might want to consider other occupations. Otherwise, let's look at the diagnosis steps for most common error—'undefined symbol'.

First, understand where the missing symbol is supposedly defined. Educated guess is usually fine. For example, a symbol named boost::system::foobar is most likely contained in the Boost.System library (and it's surprising how many folks fail to guess so). Then, find how you are supposed to link to that logical component, using documentation for the component or the corresponding Linux package. For example, you might decide to add -lboost_filesystem to the linker command line.

Second, make sure that used physical library file is the right one, and that the linker is not picking a different version of the library from a directory you don't expect. If you get error during linking of your application, you can use the -t flag for the GNU linker (or use -Wl,-t on gcc command line). This will print full paths for every library used, including those specified with the -lfoo syntax. For static linking, this will also tell which object files from the static libraries were used. If you get error when running the application, you one can use the LD_DEBUG environment variable. If you set that variable to help prior to running your program, you'll get a list of possible values. The most handy value in our case is files.

Third, if you seem to link to the right library, there are three further possibilities. First, maybe the library actually should not include the symbol. This can happen if you use wrong headers during the compilation, and can be debugged by passing the -save-temps option to gcc and checking the generated .ii file. Second, the symbol might be almost there—but slightly different—either using different calling convention (on Windows), or wchar_t mode (also on Windows) or a somewhat different types of parameters, or different namespace. In that case, you'll have to make sure the compiltation options of the application match library's requirements. Finally, it could be that the library actually lacks the symbol due to library bug, and you have to complain to maintainer. To distinguish those cases, you need to manually examine the list of library symbols. With gcc, the 'nm' command will do for static libraries, while 'readelf' can be used on shared libraries (Unix only). I don't know the best way on Windows, suggestions welcome.

That's it for the common case. Below, I list some relatively common specific problems. The list does not claim to be complete, so if you know some other cases, drop me a line.

Static linking. For static linking, the order of libraries on the command line matters, so if you don't see the linking grabbing the object file with your symbol, you might want to either reorder the libraries or use the --start-group option. See ld documentation for details and note that the performance cost of the --start-group option might not be a concern these days.

References to vtable. The GNU C++ compiler sometimes reports unresolved reference to 'vtable for SomeClass'. This generally is a pure way to say that the first non-inline method of SomeClass is not defined. See GCC FAQ

Windows DLLs. On Windows, if an application wants to use a function in DLL, then both DLL and the application should record this intention, using __declspec(dllexport) and __declspec(dllimport) pair. If either party does not do so, linker complains. With mingw, a typical error is undefined reference to `_imp___WHATEVER'. It means that the library is static, whereas the applications wants to use shared library.

Windows import libraries. On Windows, it's not possible to directly link to a DLL. Instead, an import library is created and used—typically by passing /IMPLIB option to the linker. If the linker does not report any errors, but does not produce import library either, it's a sure sign that you have not exported any function from the DLL, and have to check the logic that adds __declspec(dllexport)

64-bit compilation. When building 64-bit applications, you can get an error that say something about "relocation R_X86_64_32", and suggesting the -fPIC option. The issue here is that 64-bit applications should include only code compiled with -fPIC, and if you link against any static libraries, those libraries should also be compiled with -fPIC.

KDevelop error display

2009-05-20T20:22:00.004+04:00

For quite a while I wanted KDevelop to display compilation errors directly inside the editor, as opposed to separate window you have to click in. It works now, as shown below. This was implemented by Ivan Ruchkin, a student at Moscow State University, who will be defending a term paper about various KDevelop-related work tomorrow. The patches will be posted to appropriate mailing lists right after that.

Variable tooltips

2008-04-19T19:42:00.005+04:00

The most voted-for feature request for KDevelop3 debugger was variable tooltips. I don't think KDevelop3 will ever get them, but KDevelop4 will, as shown below.

Debugger stories: pending breakpoints

2007-12-21T21:47:00.000+03:00

KDevelop 3.5 has a subtle bug. Sometimes, when you step over a function call, you don't stop on the next line. Instead, the application is resumed until it hits a breakpoint, or exits. This bug, in fact, is consequence of how breakpoints in shared libraries are implemented.

Suppose you've just started a debugger, and try to set a breakpoint on a function in a shared library. The library itself might not be loaded yet, in which case GDB cannot find the address of the symbol to set the low-level breakpoint. To handle this case, starting with version 6.1, GDB supports pending breakpoints. Such breakpoints don't correspond to any address in program, they only keep the specified breakpoint location as string. Whenever a new shared library is loaded, GDB tries to re-parse breakpoint location again, and if that succeeds, creates an ordinary breakpoint.

Now, this does not work when using the MI interface, for a couple of reasons:

When a pending breakpoint is resolved, it is deleted, and new one is created. And GDB fails to inform MI frontend about this.
It's actually not possible to create pending breakpoint using MI at all.

Because of these issues (and a bit of historic reasons) KDevelop 3.5 simulates pending breakpoints. GDB is asked to stop whenever a shared library is loaded, and when that happens, KDevelop tries to reinsert breakpoints. This works pretty well, except for the bug I mention in the beginning. Suppose you're stepping over a function call (this uses the "next" command on GDB level). The function opens some shared library, and which point GDB stops and KDevelop tries to reinsert breakpoints. After that KDevelop would like to continue the "next" operation, but it's already aborted by GDB. All we can do is continue the program.

But it's not longer the case today. As I wrote earlier GDB was recently modified so that a breakpoint can correspond to several addresses, such as of template instantiations. A breakpoint is re-evaluated each time a shared library is loaded or unloaded, and locations are added to breakpoint and removed as appropriate, but it remains the same breakpoint. The nice side effect is that pending breakpoints are now just breakpoints with zero locations, that are reevaluated just like other breakpoints, and don't ever change their number.

In addition to that, I wrote patches to add pending breakpoint support to MI -- which mainly involved getting rid of two parallel breakpoint-setting code paths -- one for MI and one for CLI. Thanks to review of Joel Brobecker and Daniel Jacobowitz, those patches went in GDB CVS eariler this month. KDevelop 3.5 SVN was modified to automatically detect and use this GDB feature. So, if you're willing to build CVS HEAD of gdb and KDevelop from KDE 3.5 branch, you can finally have breakpoints in shared library just working.

This was probably my last KDevelop 3.5 commit. KDevelop 4 is ahead.

Breakpoints in constructors

2007-11-26T21:30:00.000+03:00

Presently, no release of GDB properly handles breakpoints in contructors. This summer, I've worked on fixing that, and while it took longer than expected, it was eventually done, just in time for Sourcery G++ Fall release. The patches were also submitted for GDB FSF, missed the window for 6.7, but will be present in 6.8 release.

The underlying problem with breakpoints in constructors was that gcc generates two distinct function bodies for a constructor. One is a regular one that constructs the entire object, including all bases. Another one constructs everything except for virtual base classes. As it happens, gcc emits both constructors even for classes that have no virtual bases at all. GDB was not prepared that a given function name or source line corresponds to several addresses in program, so it picks one. And usually it picked the wrong one.

Constructor is the most common case, but is not the only one. If you set a breakpoint in a function template, you can have multiple template instantiations that correspond to a source line. An inline function can be inlined in multiple places, and lead to exactly the same problem.

The solution, obviously, is to teach GDB that a breakpoint can correspond to several addresses, and then create multiple-location breakpoints when needed. Now, whenever a user creates a breakpoint that resolves to a source line, GDB traverses line tables for all modules, and if it finds another address for the same line, that address is added to breakpoint. For a template or inline function, you can end up with quite a lot of locations, so you can review list of locations, and disable the unwanted ones.

The nicest bit of this is interaction with shared libraries. Say, you've set a breakpoint inside function template. If you load a new shared library, and it contains an instantiation of that function template, a new location will be added to the breakpoint, transparently. If a library is unloaded, the location will become 'pending', until you load the library back.

The side effect of this work was a serious improvement in the way breakpoints in shared libraries work, but that's a topic for another post.

Debugger Stories: Stack widget

2007-02-01T00:28:00.000+03:00

In KDevelop 3.4, the stack widget was not changed much. I can remember just two changes—one that is apparent and one that is subtle.

The apparent change is that we actually parse gdb output, and show it it a readable way, while in KDevelop 3.3 the stack frame formatting was entirely at mercy of gdb's "backtrace" command.

The subtle change is at the bottom of the screenshot—that "(click to get more frame)" thing. When a program stops, KDevelop fetches very few frames from gdb. If you click on that last item, then another chunk of frames will be fetched.

This behaviour is needed for two reasons. First, if your program is stuck in infinite recursion, and you try to interrupt it from KDevelop, in KDevelop 3.3 you're out of luck. As soon as the program is interrupted, KDevelop asks gdb for the list of all frames. Since your program is in infinite recursion, the number of frames is very large, and gdb is not very speedy stack-walker. So, you get to wait 5 mins for the stack to be shown. With incremental display, in a few clicks you'll see what function went astray.

The second reason is embarassing. Even without infinite recursion, getting the list of frames from gdb takes a lot of time. Something like half-a-second for getting 30 frames is not unheard of. Ideally, we'd fix gdb, but since we need incremental fetch anyway, fetching sufficiently small number of frames initially greatly improves responsiveness.

Debugger stories: Watchpoints

2006-05-31T13:12:00.000+04:00

One of my faviourite debugger changes in KDevelop 3.4 is proper watchpoint handling. Before explaining it, some introduction is due.

Say you're debugging and see that the 'foo' field of 'pointer_to_some_data' is completely bogus. You are sure that it was valid some time ago, like when its containing object was constructed, so the question is where the corruption happened. That's exactly what watchpoints are for. You set breakpoint at a code where 'foo' is known to be valid, and then ask the debugger to stop whenever the value of 'foo' changes. The debugger in turn writes the address of 'foo' to a special processor register, and processor will call back the operating system, and then debugger, when 'foo' changes.

Except that GDB does not work this way by default. If you say:

watch pointer_to_some_data->foo

there are two interpretations. First is to stop when memory location referred to by pointer_to_some_data->foo is modified. Second is to stop when the value of the expression pointer_to_some_data->foo changes, which can happen also if pointer_to_some_data changes. Obviously, when debugging memory corruption, you care about memory address, and pointer_to_some_data is just a way to specify the memory address. Alas, by default GDB uses the second interpretation, so to set watchpoint on address you should use:

print &(pointer_to_some_data->foo)
watch *$

But the problem is not just that you'll get false hits when pointer_to_some_data changes. The thing is that if that variable is a local one, or a function parameter, then GDB will immediately remove watchpoint when you exit the containing function. So, for KDevelop user it will be like that: you pick a local variable in a variables widget, you expand it, right-click on some member, select "Toggle watchpoint", and continue. The watchpoint you've just added immediately goes away.

KDevelop 3.4 solves this problem in a radical way. All watchpoints are address watchpoints. For any expression you enter, address is computed and watchpoint is set on address. Expression without address (rvalue) can't be watched and you'll get an error message if adding watchpoints for rvalue. Additionally, when the application exits, all watchpoints are disabled, because data addresses can well be different on the next run. When user decides to enable a watchpoint, the address of expression is evaluated again, and a new watchpoints is set to that address.

Hopefully this will make watchpoints more usable for the ordinary programmer.

Introducing MI branch

2006-05-02T11:17:00.000+04:00

For recent months, I was working on an internal reorganization of KDevelop debugger, informally known as "MI branch". Now that it mostly works, it's time to describe the goals and results.

The original goal was to use a different interface with GDB, called "MI", that's specifically meant for frontends. In MI mode, gdb output can be easily parsed into DOM-like structure, and examined in a nice C++ way, something like:

(*last_stop_result)["value"]["old"].literal()

Before, KDevelop was parsing GDB output intended for humans, and could in some cases misinterpret it. Like thinking that application is running, when it's actually stopped. This unreliability was the primary reason for switching to MI.

But MI is not a silver bullet. Both John Birch (original author of debugger part), and I had reservation about maturity of MI, which proved true eventually. I'll talk about this later, but basically, using MI does not automatically make debugger better, or faster, or anything, contrary to what many think. However, since using different protocol is a big code change already, I've sneaked in a number of architectural and GUI changes, hopefully for better.

So in the end MI branch had two goals:

Fix all glitches. Do you know that in some cases KDevelop 3.3 shows only half of local variables? Or that setting watchpoint in a natural way is rarely what you want? Or that if a program is stuck in infinite recursion, KDevelop will take minutes to show the stack? Each issue is not very significant in itself, but together they make user experience not confortable.
Cleanup internal architecture. Original architecture was a bit too centralized and adding new features required a lot of work. And since many cool features come to mind, it's better be fixed quick.

The "MI branch" itself is already merged to KDevelop 3.4 branch. In future posts I'll describe all changes the debugger has compared to 3.3 release. Stay tuned.

Non-constant size

2006-04-27T13:48:00.000+04:00

Quite some time ago, when I was learning STL, all information sources stressed the importance of learning complexity guarantees that methods of various containters make. One specific subtle thing is that the std::list<>::size() method runs in linear time, not in constant time. It was explicitly designed that way for a reason, described in STL faq, but what matters to an ordinary programmer is that testing lists for emptyness should be done with the empty method, not by comparing size to zero, otherwise it's easy to kill performance.

Today, I run into another case where non-const-time size() matters. I was testing KDevelop on some testcase, and noticed that getting list of stack frames from gdb takes a lot of time. I've added some profiling code, and found that a one command takes 200ms to execute. Adding profiling code to gdb revealed that gdb itself takes some 70ms. Of course, that's not ideal, but even larger fraction of time was apparently spend in KDevelop, ehm, parsing the response.

So I've quickly put up a testcase that repeatedly parses a specific response, and ran it under callgrind. Ten minutes later I've got a profile with strlen on top. It turned out that the parsing code was using QCString and calling it's length method at least one for each token, and for certain tokens -- once for each character. The length, in turn, just calls strlen. Since the input string was 20K in size, most of runtime was spend measuring the size of that string.

Another unexpected behaviour was found in the QCString::mid function. Internally, it also calls length, and mid was called once for each token.

After uses of non-const-time methods were reduced to minimum, the parsing time my test case decreased 40x. No so bad, I think. The only problem is that time spend in gdb is still to high for a GUI, and that won't be that easy to fix.

Printf debugging 2006

2006-04-06T13:57:00.000+04:00

One of the oldest methods of debugging is "printf debugging" -- putting various print statements in the code and then staring at the output. That's useful not only if you can't use a debugger. If the program does not crash, but produces wrong results after long computation, it's hard to figure where exactly the problem lies. In that case, printing intermediate data can be a very efficient method.

The only problem is that after adding print statements the program must be recompiled, and after debugging print statements must be removed. But it's possible to make gdb into printing machine using so called "breakpoint commands". Each breakpoint can have a list of commands that will be executed when breakpoint is hit. The commands can include printing and "continue". Here's a simplified example of gdb script I've used recently:

break main.cpp:1353
commands
   print ('lvk::nm_model::NM'*)this
   printf "Entering 'run', proc %d\n", $->processor_number
   continue
end
run

After putting this to a file "script", gdb can be run as:

gdb -batch -x script name_of_program > log

producing logs of variable values as certain points of the program.

Starting with version 3.3.0, similar functionality is available in KDevelop. Just click on the "Tracing" column in breakpoints window, select variables to print and click OK.

More screenshots here and here. This is a beginning, future KDevelop version will allow to specify custom commands for breakpoints.

Unlucky numbers: 48, 58 and 388

2006-04-04T18:23:00.000+04:00

One day I've got a remarkable bug report:

We're calling the function from your library, and after 48 successfull calls, it crashes. Can you look into this?

Initially, I was curious how did they count that '48'. It turned out that the application was repatedly doing the same action, calling my code alogn the way, and counting the number of repeatitions, so '48' was the exact number, and the thing conistently crashed after 48 calls.

The bug report did not include any calling code, so I've asked for the code to be sent, and went home, and while in a bus decided that either it's fixed size buffer in the calling code, or resource leak, like file descriptors leak.

And sure thing, next morning I looked at the only thing where I used plain FILE* in order to use Bison-based parser, and there was missing fclose call. Feeling rather smart, I've sent the fixed version back.

After 30 minutes new bug report arrived saying that the code fails after 58 calls. And this time, the bug does not reproduces for me. After several tries I found out that for me, the unlucky number is actually 388, so I need to wait a bit to reproduce the bug.

This was resource leak too, though a subtle one. The library was calling external tool, and modified the PATH environment to make sure the tool is found. As the result, the length of PATH variable steadily increased, and finally some OS limit would be reached. After that the value of PATH becomes completely bogus and the external tool won't be found.

I'm really glad we have Valgrind so at least memory leaks don't require any magic to debug.

Not my bug

2005-12-17T10:12:00.000+03:00

Often most debugging time is spent of pretty uninteresting bugs.

For example, most part of last Friday I was staring into debugger backed up by MIPS simulator, trying to figure out why exactly one test of 10 run decided to crash on a MIPS board. Let me first show you the code that was found guilty in the end:


static void itoa_really(unsigned long long value, unsigned int base)
{
    static char digits[] = {'0', '1', '2', '3', '4', '5',
                '6', '7', '8', '9', 'a', 'b', 'c', 
                'd', 'e', 'f'};

    if (!value)
        return;
    else {
        long rem;
        itoa_really(value / base, base);
        rem = value % base;
        target_putchar(digits[rem]);
    }
}

This is extremely basic code, but yes, it did broke everything.

Initially, the crash happened on a real MIPS board, on a pretty complex test. It was reduced to a test printing just two 64-bit values, and crash depended on the printed values. Say, printing 0 worked, but printing 0x11223344556677 crashed. It was not possible to debug the problem on the board, and the few floating licences for simulator were in use, so I tried to solve the problem by poking around. At one time I've added an extra line of code before call to "target_putchar", and the line was:


rem = 3;

Strangely, the crash was gone.

At this point I though that maybe there's some really wrong with 64 on 32 division, and 'rem' can become wrong, so I replace that "rem = 3" line with:


if (rem < 0) { rem = 0; }
if (rem > 15) { rem = 15; }

The crash appeared again.

Another try was:


if (rem < 3) { rem = 3; }
if (rem > 3) { rem = 3; }

and the crash was still there.

Finally, with:


if (rem <= 3) { rem = 3; }
if (rem > 3) { rem = 3; }

everything worked. Of course, all values was printed as "3333.....333", but it did not crash. Completely buffled, I decided simulator is the only help and eventually we've grabbed the license.

A couple of hours later, I found the one-character fix (literally). The linker config file specified mere 1KB of stack size, and when printing too large values, itoa_really recursed too deep, overflowing the stack, and overwriting a bunch of program variables. Changing to 4KB of stack set it all right. And what's even more funny, I never ever touched that linker config file, and have no idea what kind of programs are supposed to work on such stack space diet.

Whatever you name them

2005-12-13T14:45:00.000+03:00

I've just wrote the following code:

void on_vector_write(unsigned address, unsigned address)
    {
        if (w_on_vector_write)
            w_on_vector_write(address,
    }

It's not complete -- I was just about to pass a second parameter to "w_on_vector_write" when I realized that the two parameters of my function have the same name. But heh, I've just copy-pasted that signature, and the code I've pasted from certainly compiles. Here's how that compiling code looks:

boost::function<void (unsigned address,unsigned address)> 
    on_vector_write;

Apparently, gcc does not care about parameter names that are used when forming function type. And it does not care about function names in function prototypes either, even in 4.0.

Where am I?

2005-10-27T15:27:00.000+04:00

How can an application or a library find out its own location on Linux?

Suppose you want an application for Linux to work after being just unpacked to some directory. No setting of COOL_APP_HOME environment variable, no creation of ~/.coolapprc, nothing. If the application is one self-contained binary, no problem, but if there are some resources (icons, or translations, or random data files), you need to find them somehow. And since the only action user did was unpacking the application, you can only find resources by using a path relative to the application's path. But finding application path is not straightforward.

The obvious approach is using argv[0]. But not quite simple, because argv[0] can be:

An absolute path. You just strip file name from it and get the path to the application.
A relative path. You need to join current directory with that relative path, and strip file name.
Application name without the path. Could happen if application was found via the PATH environment variable. It's necessary to iterate over all PATH elements, trying to find the application there.
Anything. The value of argv[0] is specified in exec* call and can be absolutely anything.

A more reliable method is using the /proc filesystem. The /proc/<pid>/exe is a symbolic link the the application, and /proc/self is the same as /proc/<pid of current application>. So, calling readlink on /proc/self/exe gives the desired effect.

But it does not work for shared libraries. Shared library can have its own resources, and might want to find them relatively to library path. Using /proc/self/exe will give the path to the application, not to the library. The solution here is the dladdr function, which is Linux extension to the dynamic loader interface. Here's example use:

std::string where_am_i()
{
    DL_info info;
    if (dladdr( &where_am_i, &info ) == 0)
    {
        return info.dli_fname; 
    }
    ....
}

The function takes a code address, and returns information about shared library this address belongs to. So, if where_am_i function is defined in a shared library, the above code will return the path to that library. Unfortunately, this works only for dynamic libraries, but not for application. So, for a really reliable solution one has to combine the /proc/self/exe trick with the dladdr trick.

The only problem is that both tricks are specific to Linux. Why such a basic functionality not in POSIX?

The last interesting case is when the "resource" your applications uses is a shared library with on-startup linking (not explicit dlopen linking). The path to the library should be added to dynamic linker search path before the application is started, so the above tricks won't help. Forgunately, it's not necessary to create helper applications or scripts, you just need an extra options when linking:

g++ -o executable -Wl,-R -Wl,'$ORIGIN' executable.o libhelper.so

The -Wl,-R -Wl,'$ORIGIN' options adds a new element "$ORIGIN" to dynamic library search path in the executable, and the dynamic linker will replace $ORIGIN with the path of the executable.

With all those tricks in hand, it's not longer needed to know beforehand the directory where the application will be installed. But I'd still prefer nice builtin support, like Mac OSX bundles.

Black or white?

2005-10-04T15:14:00.000+04:00

What's better: black box testing, or white box testing? In general, neither, but sometimes peeking at internals can be a great help.

One of the project at work now is writing a compiler for simplified C (basically, C without structures). And one recent addition was declaring several variables in one declaration. The existing test was:

int32 v, v2, v3;

int32 main()
{
    v3 = 15;
    v2 = v = 10;
    printf("Result = %d\n", v + v2 + v3);
    return 0;
}

and it worked immediately. But there's was a bug, and just as experiment, I've asked the author of the test to find the bug. His attempts were:

Using duplicate name of variable: int32 v, v2, v3, v;. That produced an error, as expected.
Defining extra local variable "v2". Still no problems.
Initializing some of the variables at definition point, not inside the function.
Trying different type of variables.
Moving the code from main to another function.

At this point, he gave up. The real problem occured at this example:

int32 xi = 100, i = xi + 5;

int32 main()
{
    printf("Result = %d\n", i);
}

and was caused by creating variables in the reverse order. The language grammar is written in the way that makes traversal in the reverse order more natural. And so variable i was initialized before variable xi. Honestly, I can't blaim the tester. It's a kind of bug you can think about only if you know that nonterminals can be left-recursive and right-recursive. Or see the code.

1 + 2

2005-07-21T18:18:00.000+04:00

I've just got the following:

(gdb) target remote :1234
Remote debugging using :1234
main () at main.cpp:5
5       {
(gdb) p add(1, 2)
$1 = 3

As you see, using the gdb debugger I've evaluated expression add(1,2), where function add presumably adds two numbers, and got the right result. What's interesting in this? There are two interesting things:

It's gdb port to a new target.
The remote side is not a hardware board -- it's our simulator, which was taught to talk using gdb's remote protocol

However simple the example seems, it involves several steps:

First of all, gdb must load the symbol tables. Othewise, it won't know that add is a function. That did not work out of box, for example gdb assumed that program can't start at address 0.
After connecting to the target, gdb asks about the value of program counter. This requires support for appropriate protocol command. Also, our simulator took shortcuts and did not even maintain the program counter!
To call a function, the arguments are pushed to a temporary memory area. This requires code that knows calling convention for the target, and memory writing support.
After that, a fake return address is placed to a stack (typically, entry point of the program), and a breakpoint is set to that return address. So this requires working breakpoints in the simulator.
Then, debugger changes program counter to the address of add and resumes program execution.
After hitting breakpoint, the return value of the function is extracted, which again requires knowing calling convention.

So, it's not just a poor man's calculator, it's also a test for a good deal of debugger functionality. There's also stack frame handling (up/down/where/finish), and printing of complex data types (structures/arrays), but believe me, that works as well. It looks like my 3-month gdb and simulator hacking comes to an end, and I'll spend more time on more interesting things like improving KDevelop's debugger frontend.

Spurious wakeups

2005-07-06T13:13:00.000+04:00

One of the two basic synchronisation primitives in multithreaded programming is called "condition variables". Here's a small example:

bool something_happened;
boost:::mutex m;
boost:::condition c;
void thread1()
{
     boost::mutex::scoped lock(m);
     while(!something_happened)
     {
        c.wait(m);
     }
}
void thread2()
{
      // do lots of work
      boost::mutex::scoped lock(m);
      something_happened = true;
      c.notify()
}

Here, the call to "c.wait()" unlocks the mutex (allowing the other thread to eventually lock it), and suspends the calling thread. When another thread calls 'notify', the first thread wakes up, locks the mutex again (implicitly, inside 'wait'), sees that variable is set to 'true' and goes on.

But why do we need the while loop, can't we write:

if (!something_happened)
    c.wait(m);

We can't. And the killer reason is that 'wait' can return without any 'notify' call. That's called spurious wakeup and is explicitly allowed by POSIX. Essentially, return from 'wait' only indicates that the shared data might have changed, so that data must be evaluated again.

Okay, so why this is not fixed yet? The first reason is that nobody wants to fix it. Wrapping call to 'wait' in a loop is very desired for several other reasons. But those reasons require explanation, while spurious wakeup is a hammer that can be applied to any first year student without fail.

The second reason is that fixing this is supposed to be hard. Most sources I've seen say that fixing that would require very large overhead on certain architectures. Strangely, no details were ever given, which made me wonder if avoiding spurious wakeups is simple, but all the threading experts secretly decided to tell everybody it's hard.

After asking on comp.programming.thread, I at least know the reason for Linux (thanks to Ben Hutchings). Internally, wait is implemented as a call to the 'futex' system call. Each blocking system call on Linux returns abruptly when the process receives a signal -- because calling signal handler from kernel call is tricky. What if the signal handler calls some other system function? And a new signal arrives? It's easy to run out of kernel stack for a process. Exactly because each system call can be interrupted, when glibc calls any blocking function, like 'read', it does it in a loop, and if 'read' returns EINTR, calls 'read' again.

Can the same trick be used to conditions? No, because the moment we return from 'futex' call, another thread can send us notification. And since we're not waiting inside 'futex', we'll miss the notification. So, we need to return to the caller, and have it reevaluate the predicate. If another thread indeed set it to true, we'll break out of the loop.

So much for spurious wakeups on Linux. But I'm still very interested to know what the original reasons were.

Environment variables gotcha

2005-04-15T21:37:00.000+04:00

The Debian Policy requires that applications do not depend on environment variables for proper operation. Why? They say that /etc/profile is not supported by all shells (hmm... is there anything but bash?), and that the file should not be modified at all, but there's also another simple reason.

If you run:

$ su root
# apt-get install whatever
$ whatever

then any environment variable setting added to /etc/profile won't affect the current session, only future ones. And there's no way around this. So if whatever needs some environment variables, it will just break.

In my case, "whatever" used environment variables to find its icons, which produced marvellous results:

Just multiplication

2005-04-08T14:37:00.000+04:00

How easy is it to multiply two numbers?

Recently, I've discovered that our fast emulator handles the multiplication in a completely wrong way. Well, multiplication is a very common operation, and even trivial testing should have found the bug. But there's one detail -- the processor does not have a multiplication instruction at all.

Instead, there are two instructions -- "first multiplication step" (MLF) and "next multiplication step" (MLS). To multiply two 32-bit numbers one has to execute MLF, and then to execute MLS 15 times. The documentation says this, C compiler generates this sequence, and everywhere I looked it was implemented this way. So, I decided to ignore MLS, and implement MLF as a regular multiplication.

And there were just one place where this approach failed, because there were 11 MLS instructions, not 15. To explain why this "incorrect" multiplication is need, I need to first explain the underlying algorithm.

Say you need to multiply 101 (binary) by 11100. Recalling school math that would be:

101 * 11100 -------------- 101 * 0 + 1010 * 0 + 10100 * 1 + 101000 * 1 + 1010000 * 1

= 10001100

However, 11100 can be represented as 100000 - 100. So:

         101   
   *   11100
------------
-      10100    * 1
+   10100000    * 1

Both approaches can be implemented as a loop over bits of the second operand. In the first approach you look at the lowest bit of the second operand, and if it's non-zero, add the first operand to the result. The first operand is then shifted left by one bit.

In the second approach when the lowest bit of the second operand is non-zero and the previous bit was zero, we substract the first operand. When we see 1->0 transition, we add the first operand. And the first operand is shifted after each bit, too.

This is called Booth algorithm, and it's primary purpose was to reduce the number of additions and substractions, because on older computers those operations took more time then shifts. In the example above, we save one add operation. The second advantage, more relevant today, is that Booth algorithm works fine with negative numbers. This is not obvious, but it does. See here.

The MLF and MLS instruction implement the modified Booth algorithm, that handles two bits at one step -- so we need 16 steps for 32 bit numbers. In the specific processor, each step shifts the second operator right by 2 bits, and new bits of the result appear from the left. And now the key trick -- suppose that input operands are unsigned and limited to 8 bits. Then the result will contain at most 16 bits. After 8 steps will will compute those 16 bits, but they'll be in the upper half of the register. Next 8 steps will just slowly shift them to the right position. So if you don't mind getting shifted result, you can get it in half the time. As an example, if you want to compare a*b with c*d, the extra shift does not matter.

Cool, isn't it? But don't ask how long it took me to find the single place where this trick was used!

Duplicate function bodies

2005-03-24T13:22:00.000+03:00

A couple of days ago I've learned that the Microsoft linker can merge functions with binary identical bodies. Looks rather good idea, especially with templates, and it seems that gcc does not implement this. Why don't estimate possible size saving?

Basically, we just need to get all function bodies from an object file or shared library and check for duplicates. The only thing to watch out are relocations. Consider this code:

extern int a, b;
int foo() { return a; }
int bar() { return b; }

The binary code for both functions will be identical:

   _Z3foov:
55                    pushl   %ebp
89E5                  movl    %esp, %ebp
A1000000              movl    a, %eax
00
5D                    popl    %ebp
C3                    ret

But later, either during static link or during application startup, those eight zeros will be replaced with addresses of variables a and b, which are obviously different.

Luckily, this is easy to fix. When compiling with -fPIC, the compiler will produce code that's not modified during startup. This means that two identical function bodies will remain identical. Since all shared libraries are built with -fPIC, we can safely use shared libraries for testing.

However, running the test program on a couple of template-extensive Boost libraries produce rather discouraging results.

Boost.Python:

461 functions found
2073 unique function bodies
205589 bytes of function bodies
Function merging would have saved 3898 bytes

Boost.Regex:

3313 functions found
2782 unique function bodies
484635 bytes of function bodies
Function merging would have saved 7808 bytes

Most of the functions with duplicate bodies were rather small in size -- 5-10 bytes -- basically empty. Probably, there's some other variable I did not consider. Or maybe gcc's register allocator is non-deterministic. What is the actual problem is a topic for some future post.

As an aside, I've used the BFD library to read the files in ELF format, and got rather mixed feelings. On one hand, I've did what I wanted. On the other hand, the library is horrible. The documentation structure is the worst I've ever seen, and it's very hard to find anything. There's no complete compilable example to get started. The interface is terrible C -- with the need to manually allocate memory all over. And finally, I was hit by two weird things.

First, is that the following reasonably-looking code does not work:

bfd* object = bfd_openr("object.o", "i686-pc-linux-gnu");
assert(object);
asection* s = bfd_get_section_by_name(object, ".text");

The second call just segfaults. Changing the code to

bfd* object = bfd_openr("object.o", "i686-pc-linux-gnu");
assert(object);
assert(bfd_check_format (object, bfd_object));
asection* s = bfd_get_section_by_name(object, ".text");

makes it work fine. That's just voodoo.

Another problem, is that is not possible to get the size of a symbol. Really, this basic information can't be obtained via BFD's public interface.

Why constructors crash

2005-03-21T19:35:00.000+03:00

Of course, C++ constructors can crash for absolutely any reason. The interesting reason is member initialization. Consider this code:

C::C(const std::string& a) : a(a) {}

which is perfectly OK. The C++ standard allows to use parameter 'a' when initializing member 'a'. But consider the following example:

C::C(const std::string& acuracy) : accuracy(accuracy) {}

A small typo causes initialization of the member with itself, which can likely crash. This is one reason why adding "m_" prefix to member names is a good idea.

Just now, I've seen a more complicated example. A colleague first shown a code like in the first example and asked if it's OK. I immediately replied that it's OK unless there's a typo. But the real crash was a bit more contrived:

class Entry {
public:
     Entry(const std::string& EntryId) : EntryId(EntryId) {}
     std::string EntryId;
};
class LogEntry : public Entry
{
public:
    LogEntry(const std::string& Id): Entry(EntryId) {}    
};

Here, if the parameter of the second constructor was named "EntryId", everything would work. As it stands, the base constructor is passed the base member as initializer and again the member is initialized with itself.

Moral of the story

Use the "m_" prefix
Make all data members private

Outputting T

2005-03-18T10:28:00.000+03:00

I'm positively shocked. In C++, there's no easy way to write a template function with one parameter that will output that parameter to a stream, with full precision.

If you write:

std::cout << t;

then you'll be using the default stream precision, which is 6. And 't' can be double with 10 digits after the dot.

If you write:

std::cout << setprecision(10000) << t;

you'll suddenly get too many digits. For outputting "1.1", you'll get:

1.100000000000000088817841970012523233890533447265625

even though real precision of double is 15-16 digits.

If you write:

std::cout << setprecision(fancy_formula_involving(numeric_limits<T>::digits) << t;

the code won't compile if T is "char[N]". And if numeric_limits is not specialized for a given T, results can also be strange.

Oops!

Generalizing from examples

2005-03-16T15:55:00.000+03:00

Over time I wrote quite a lot of C++ code that generates other C++ code. At work I generate C++ from assembler, and I also worked on a parser generator called Whale. Code generation is a powerful approach, as shown by some other examples. And unlike template metaprogramming it does not stress today's compilers too much (for example, compilation speed is a recurring topic on Boost.Spirit mailing list.

But it's damn hard to write the code generator. When writing C++ code as a C++ literal, the look of the code is so strange that typos can hide anywhere. Then you build the code generator, use it to produce test code, and it fails to compile. And you're back to the beginning, hunting for missing semicolons.

The simple solution I've recently found is that new functionality should never be directly implemented in a code generator. First, you need to take the generated code and modify it, despite comments warning you that all changes will be lost. Once you've modified the generated code and it works, it's very easy to bring modifications back to code generator -- it can be even done by regex in emacs. And the generated code will work.

This brings us to the topic of the article. It's hardly a good idea to use very generic solution without trying specific examples. And an example is better that a generic advice, so here's another example: don't write a C++ template function from scratch. First write non-template function and debug it, and only then add template declaration and try with different template parameters.

One thing at a time

2005-03-12T03:36:00.000+03:00

Changing too many things at the same time can easily get one into a problem.

My project at work is essentially a very fast emulator, which takes a program for a certain processor in source form (C++ and assembler) and creates a program which can be executed on a regular PC. Until recently, processing of assembler and C++ sources was radically different. That lead to a number of problems and we decided to change the approach and compile C++ into assembler using the provided SDK. Then we'll get only assembler sources to process.

Roughly at the same time, we got new SDK, and I've decided to try it. The great news were that the assembler can be run under Wine without problems. Excellent, so I've switched to this new SDK immediately.

But then, I've also inadvertently updated my Boost copy.

As the net result, I have a number of failing tests with the new version of the program, new version of SDK (which generates somewhat different code) and new version of Boost, and no clue where to start debugging.

Of course, at least the problem with Boost could have being prevented by using Subversion and reporting revision number during nightly build, but one thing at a time -- proper handling of 3rd party dependencies is a topic for another post.